// 求负环时可以使用栈
// 平常使用要用队列

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>

// using namespace std;

constexpr int N = 2E5 + 5, M = N * 2;

int h[N], e[M], w[N], ne[M], idx;

void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int st[N];
int dist[N];
int cnt[N];

bool spfa(int start, int n) {
	memset(dist, 0x3f, sizeof dist);
	
	std::queue<int> que;
	que.push(start);
	st[start] = true;
	dist[start] = 0;
	
	while (!que.empty()) {
		int t = que.front();
		que.pop();
		st[t] = false;

		for (int i = h[t]; ~i; i = ne[i]) {
			int j = e[i], d = w[i];
			if (dist[j] > dist[t] + d) {
				dist[j] = dist[t] + d;
				cnt[j] = cnt[t] + 1;
				if (cnt[j] >= n) {
					return false;
				}
				if (!st[j]) {
					st[j] = true;
					que.push(j);
				}
			}
		}
	}
	
	return true;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	int n, m, s;	
	std::cin >> n >> m >> s;

	std::memset(h, -1, sizeof h);
	for (int i = 0; i < m; ++i) {
		int u, v, w;	
		std::cin >> u >> v >> w;
		add(u, v, w);
		// add(v, u, w);
	}

	bool flag = spfa(1, n);
	
	if (flag) {
		for (int i = 1; i <= n; ++ i) {
			std::cout << dist[i] << " ";
		}
	}
	
	return 0;
}

/*
6 10
0 1 1
0 5 4
0 2 2
1 3 2
1 2 1
2 3 1
2 4 3
3 4 1
3 5 3
4 5 1
*/

// 0 1 2 3 4 4
